#!/usr/bin/env python
import math
import sys
from operator import itemgetter
#===============================================================================
# Implements a doubly linked list for a spacesaving structure
#===============================================================================
debug = False

class Bucket :
	def __init__(self, value=1, prev=None, next=None):
		self.value = value # upper limit of
		self.elements = {}
		self.next = next
		self.prev = prev

	def __str__(self):
		return "bucket: {0}\n elements: {1}".format(self.value, self.elements.values())

	def append(self, element):
		self.elements[element[0]] = element # maps element key to element

	def update(self, element):
		self.elements[element[0]] = element

	def has_elements(self) :
		return len(self.elements) > 0
	def remove (self, element):
		self.elements.pop(element[0])

	def set_prev(self, _prev):
		self.prev = _prev

	def set_next (self, _next):
		self.next = _next
	def get_min(self):
		min = self.elements.items()[0]
		for item in self.elements.items()[1:] :
			if (item[1][1] < min[1][1]) :
				min = item
		return min[1]

class DoublyLinkedList :
	def __init__(self):
		self.first = None # First bucket -> bucket with lowest value
		self.elements = {} # maps element key to bucket
		self.buckets = {} # maps bucket value to bucket

	def __len__(self):
		return len(self.elements.keys())

	def __str__(self):
		out = "\n"
		_bucket = self.first
		while (_bucket != None) :
			out +=  str(_bucket)
			if _bucket.prev != None :
				out += "\n prev :{0}".format(_bucket.prev.value)
			else :
				out += "\n prev : None"

			if _bucket.next != None :
				out += "\n next {0}".format(_bucket.next.value)
			else :
				out += "\n next None"

			_bucket = _bucket.next
		return out

	def buckets_to_string(self):
		out = ""
		for key, bucket in self.buckets.items() :
			out += "bucket: %s next " % str(key)
			if bucket.next != None :
				out += str(bucket.next.value)
			else :
				out += "None"
			out += "\n"
		return out

	#===========================================================================
	# Add element to streamsummary
	#===========================================================================
	def add_element(self, element):
		key = int(math.ceil(element[1]))
		#self.pr_to_stderr("add el. key ", element)
		if not self.elements.has_key(element[0]) :
			#self.pr_to_stderr("el not in SS")
			if not self.buckets : # no buckets created.
				self.buckets[key] = Bucket(value=key) # insert bucket with value = key
				self.elements[element[0]] = self.buckets[key] # add element to self.elements
				self.buckets[key].append(element) # add element to bucket's elements
				self.first = self.buckets[key]
			elif key not in self.buckets :
				#self.pr_to_stderr("no bucket for el", "")
				_bucket = self.first
				while (_bucket.next != None and _bucket.next.value < key) :
					_bucket = _bucket.next
				self.buckets[key] = Bucket(value=key, prev=self.buckets[_bucket.value]) # insert bucket with value = key

				if _bucket.next != None :
					self.buckets[key].next = self.buckets[_bucket.next.value]
					self.buckets[_bucket.next.value].set_prev(self.buckets[key])
				self.buckets[_bucket.value].set_next(self.buckets[key])
				self.elements[element[0]] = self.buckets[key] # add element to self.elements
				self.buckets[key].append(element) # add element to bucket's elements
#			   if _bucket == self.first :
#				   self.first = self.buckets[key] # set new min bucket
			else :
				#self.pr_to_stderr("buckets exists", "")
				self.elements[element[0]] = self.buckets[key] # add element to self.elements
				self.buckets[key].append(element) # add element to bucket's elements

		#self.pr_to_stderr("prev = ", str(self.buckets[key].prev == None))
		#self.pr_to_stderr("next = ", str(self.buckets[key].next == None))


	#=======================================================================
	# Increase element by adding weight, epsilon and assign to right bucket
	#=======================================================================
	def increase_element(self, element):
		#self.pr_to_stderr("increase el ", element)
		old_element = self.elements[element[0]].elements[element[0]]
		current_bucket = self.elements[old_element[0]] # get current bucket of element
		#self.pr_to_stderr("prev = ", str(current_bucket.prev == None))
		#self.pr_to_stderr("next = ", str(current_bucket.next == None))
		new_weight = old_element[1] + element[1]
		new_key = int(math.ceil(new_weight))
		#self.pr_to_stderr("oldmin ", self.first.value)
		#self.pr_to_stderr("old key", current_bucket.value)

		#self.pr_to_stderr("new key ", new_key)
		if self.buckets.has_key(new_key) :
			#self.pr_to_stderr("new_key exists: ", "")
			new_element = (element[0], new_weight, old_element[2])
			if current_bucket.value != new_key :
				self.elements[element[0]] = self.buckets[new_key]
				self.buckets[new_key].append(new_element)
				current_bucket.remove(old_element)
			else :
				self.buckets[new_key].update(new_element)
		else :
			#self.pr_to_stderr("new_key !exists", "")
			new_element = (element[0], new_weight, old_element[2])
			_bucket = current_bucket

#			while (_bucket.next != None and _bucket.value < new_key) :
			while (_bucket.next != None and _bucket.next.value < new_key) :
				_bucket = _bucket.next

			#self.pr_to_stderr("insertion bucket", _bucket.value)
			self.buckets[new_key] = Bucket(value=new_key, prev=self.buckets[_bucket.value])

			if (_bucket.next != None) :
				#self.pr_to_stderr("new_key.next : ", _bucket.next.value)
				self.buckets[_bucket.next.value].set_prev(self.buckets[new_key])
				self.buckets[new_key].set_next(self.buckets[_bucket.next.value])

			self.buckets[_bucket.value].set_next(self.buckets[new_key])

			self.elements[element[0]] = self.buckets[new_key]
			self.buckets[new_key].append(new_element)
			self.buckets[current_bucket.value].remove(old_element)

		#self.pr_to_stderr("oldmin ", self.first.value)
		#self.pr_to_stderr("old key", current_bucket.value)

		if not current_bucket.has_elements() :
			#self.pr_to_stderr("curr bucket empty\n")
#			#self.pr_to_stderr("curr.prev", current_bucket.prev)
#			#self.pr_to_stderr("curr.next", current_bucket.next)
			if current_bucket == self.first :
				#self.pr_to_stderr("is first\n")
				self.first = self.buckets[current_bucket.value].next
				self.buckets[self.first.value].set_prev(None) # set prev = None for new min bucket
			else :
				self.buckets[current_bucket.value].prev.set_next(self.buckets[current_bucket.value].next)
				if self.buckets[current_bucket.value].next!= None :
					self.buckets[current_bucket.value].next.set_prev(self.buckets[current_bucket.value].prev) # update curr.prev

			del self.buckets[current_bucket.value]


	#===========================================================================
	# Return true if summary contains key
	#===========================================================================
	def has_element(self, key):
		return key in self.elements

	#===========================================================================
	# Replace current element with minimum weight with min_new element
	#===========================================================================
	def replace_min(self, min_new):
		min_curr = self.get_min_element()
		#self.pr_to_stderr("replace min. Curr: ", min_curr)
		min_new = (min_new[0], min_new[1] + min_curr[1], min_curr[1])
		self.add_element(min_new)

		self.buckets[self.first.value].remove(min_curr)
		self.elements.pop(min_curr[0]) # remove curr_min from elements

		if not self.get_min_bucket().has_elements() :
			curr_min_bucket = self.get_min_bucket()
			self.first = self.buckets[curr_min_bucket.next.value] # set new min bucket
			self.buckets[self.first.value].set_prev(None) # update new min
			del self.buckets[curr_min_bucket.value] # remove bucket

	def addAll(self, list):
		for element in list :
			self.add_element(element)

	def get_elements(self):
		return self.elements

	def get_summary(self, type):
		if type == 'list' :
			return self.get_element_list()
		elif type == 'dict' :
			return self.get_dict_summary()

	def get_dict_summary(self):
		D = {}
		_bucket = self.first
		while _bucket != None :
			D.update(_bucket.elements)
			_bucket = _bucket.next
		return D

	def get_element_list(self):
		_bucket = self.first
		elements = []
		while _bucket != None :
			elements.extend(set(_bucket.elements.values()))
			_bucket = _bucket.next
		return elements

	def get_bucket_el_keys(self):
		_bucket = self.first
		count = 0
		keys = []
		while (_bucket != None) :
			keys.extend(set(_bucket.elements.keys()))
			if count > len(self.buckets.keys()) :
				#self.pr_to_stderr("infinite loop: ", str(count))
				sys.exit()
			_bucket = _bucket.next
			count += 1
		return keys
	#===========================================================================
	# Return bucket with minimum value
	#===========================================================================
	def get_min_bucket(self):
		return self.first
	#===========================================================================
	# Return element with minimum weight
	#===========================================================================
	def get_min_element(self):
		return self.first.get_min()

	def pr_to_stderr(self, key, error=None):
		if debug :
			print >> sys.stderr, key, error
	def clear_summary(self):
		self.first = None # First bucket -> bucket with lowest value
		self.elements = {} # maps element key to bucket
		self.buckets = {} # maps bucket value to bucket

class StreamSummary(DoublyLinkedList):
	def __init__(self):
		DoublyLinkedList.__init__(self)
#	   super(StreamSummary,self).__init__()
